package dynamicprogramming

// 拆分整数，使乘积最大化
func integerBreak(n int) int {
	// 1 dp[i] 表示拆分i可以获得的最大乘积
	// 2 dp[i] 如何求  推导   j*(i-j)直接相乘  j*dp[i-1]
	if n<=1 {
		return n
	}
	dp := make([]int, n+1)
	dp[0] = 0
	dp[1] = 1
	// n>=2
	dp[2] = 1
	for i:=3;i<=n;i++{
		for j:=1;j<=i-1;j++{
			// * (i - j) 是单纯的把整数拆分为两个数相乘
			//j * dp[i - j]是拆分成两个以及两个以上的个数相乘
			dp[i] = max(dp[i],max(j*(i-j), j*dp[i-j]))
		}
	}
	return dp[n]
}

func max(a,b int) int{
	if a>b {return a}
	return b
}
// func integerBreak(n int) int {
//     /**
//     动态五部曲
//     1.确定dp下标及其含义
//     2.确定递推公式
//     3.确定dp初始化
//     4.确定遍历顺序
//     5.打印dp
//     **/
//     dp:=make([]int,n+1)
//     dp[1]=1
//     dp[2]=1
//     for i:=3;i<n+1;i++{
//         for j:=1;j<i-1;j++{
// // i可以差分为i-j和j。由于需要最大值，故需要通过j遍历所有存在的值，取其中最大的值作为当前i的最大值，在求最大值的时候，一个是j与i-j相乘，一个是j与dp[i-j].
//             dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]))
//         }
//     }
//     return dp[n]
// }
// 贪心法
// 每次拆成n个3，如果剩下是4，则保留4，然后相乘，但是这个结论需要数学证明其合理性！
// class Solution {
// 	public:
// 		int integerBreak(int n) {
// 			if (n <= 3) return 1 * (n - 1);
// 			vector<int> dp(n + 1, 0);
// 			dp[1] = 1;
// 			dp[2] = 2;
// 			dp[3] = 3;
// 			for (int i = 4; i <= n ; i++) {
// 				for (int j = 1; j < i - 1; j++) {
// 					dp[i] = max(dp[i], dp[i - j] * dp[j]);
// 				}
// 			}
// 			return dp[n];
// 		}
// 	};